package com.hy.backtracking3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subset2 {


    /**
     * 90.子集II
     * 力扣题目链接
     *
     * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     *
     * 说明：解集不能包含重复的子集。
     *
     * 示例:
     *
     * 输入: [1,2,2]
     * 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
     *
     * 思路
     * 做本题之前一定要先做78.子集。
     *
     * 这道题目和78.子集区别就是集合里有重复元素了，而且求取的子集要去重。
     *
     * 那么关于回溯算法中的去重问题，在40.组合总和II中已经详细讲解过了，和本题是一个套路。
     *
     * 剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。
     *
     * 用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）
     *
     */
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> getSubset2(int [] num,int startIndex){
        Arrays.sort(num);
        if (num.length == 0){
            res.add(new ArrayList<>());
        }
        subset2(num,startIndex);
        return res;
    }

    public void subset2(int [] num,int startIndex){
        res.add(new ArrayList<>(path));
        if (startIndex >= num.length){
            return;
        }
        for (int i = startIndex; i < num.length; i++) {
            // 排序 去重
            if (i > startIndex && num[i-1] == num[i]){
                continue;
            }
            path.add(num[i]);
            // 回溯
            subset2(num,i+1);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Subset2 subset2 = new Subset2();
        int [] num = {1,2,2};
        System.out.println("res: "+subset2.getSubset2(num,0));
    }
}
